The broad long-term objective of this study is to develop non-toxic anticancer and immune-enhancing dietary supplements for the treatment of cancer and immune-deficiency diseases. The specific objective is to test whether a specific mixture of "Selected Vegetables and Herbs Mix (SV)", which consists of non-toxic botanicals containing known anti-cancer and/or immune enhancing components, may prolong the survival of stage 111B/IV non-small cell lung cancer (NSCLC) patients in a phase 3 clinical trial. NSCLC causes more than 150,000 annual deaths in the US and is the leading cause for cancer-related death in the nation. The efficacy of current therapies is marginal. Tumors respond poorly to chemotherapy, whose toxicity adds misery to patients. The median survival time (MST) of stage IIIB/IV NSCLC patients has remained under 9 months. In 2 recent phase I/II clinical trials, SV was shown to improve MST of stage Ill/IV and IIIB/IV NSCLC patients to 15.5 month and to 33.5 month respectively. SV was shown to be non-toxic, improved the Karnofsky Performance Status (KPS) and better maintained the patients' body weight. These results are encouraging but must be confirmed in a large scale randomized clinical trial. In this study the MST will be evaluated trimonthly up to 36 months after the entry of the last patient. Three hundred twenty stage IIIB/IV NSCLC patients with good performance status (ECOG Performance Status >0 or 1) will be offered chemotherapy treatment (gemcitabine+cisplatin (GC)); and within each of the strata, randomized to add active SV or placebo SV to their daily diet. Local treatments, radiotherapy and/or surgery, will be used concurrently if indicated. The primary goal of the study is to test the hypothesis that SV may prolong the survival of stage IIIB/IV NSCLC patients. The tumor response to SV and GC and the quality of life of the patients in each stratum will be evaluated and compared. Given the high incidence and poor prognosis of NSCLC, modest improvements in survival can be translated into many thousands of useful added years for these patients.